package 滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * @Date 2024/9/1 22:19
 * @description: 无重复字符的最长子串(字节)
 * . https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ (中等)
 * @Author LittleNight
 */
public abstract class likou209 {

    public static void main(String[] args) {
        String s = "admin";
        String s1 = "admin";
        System.out.println(s == s1);
        System.out.println("Admin".toLowerCase() == "admin");
    }

    // 抽象方法不能加 {}
    public abstract void test();


    // todo 正确写法
    // 练习, 无重复的最长子串
    // 滑动窗口: 1. 进窗口 2. 判断 3. 出窗口.  更新结果
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        Map<Character, Integer> hash = new HashMap<>();
        int left = 0, right = 0, ret = 0;
        // 注意遍历的是 right
        for (right = 0; right < n; right++) {
            char c = ch[right];
            // 1. 进窗口.
            hash.put(c, hash.getOrDefault(c, 0) + 1);
            // 2. 判断. 因为每次都会判断, 因为只在乎结果, 不在乎哈希表中存的
            // 所以用 if 也是可以的, 就也不用 hash中c的个数减一了.
            while(hash.get(c) > 1) {
                // 出窗口. 这里是不等于, 一直要找到重复的字符的地方.
                while(ch[left] != c) {
                    // 直接移除就可以了. 因为就出现了一次
                    hash.remove(ch[left]);
                    left++;
                }
                // 多走一步才是正确结果
                left++;
                hash.put(c, hash.getOrDefault(c, 0) - 1);
            }
            // 4. 更新结果 (不能放在判断里面, 因为有的是第一次出现. 每次多一个就进行更新.
            // 要是放在里面出窗口的时候在更新, 假如全是无重复的就不会更新结果了)
            ret = Math.max(right - left + 1, ret);
        }
        return ret;
    }

    // todo 错误写法
    // 练习, 无重复的最长子串
    // 滑动窗口: 1. 进窗口 2. 判断 3. 出窗口.  更新结果
    public int lengthOfLongestSubstring222(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        Map<Character, Integer> hash = new HashMap<>();
        int left = 0, right = 0, ret = 0;
        // 注意遍历的是 right
        for (right = 0; right < n; right++) {
            char c = ch[right];
            // 1. 进窗口.
            hash.put(c, hash.getOrDefault(c, 0) + 1);
            // 2. 判断. 因为每次都会判断, 所以用 if 也是可以的
            while(hash.get(c) > 1) {
                // 出窗口
                while(ch[left] != c) {
                    // 直接移除就可以了
                    hash.remove(ch[left]);
                    left++;
                }
            }
            // 4. 更新结果 (不能放在判断里面, 因为有的是第一次出现. 每次多一个就进行更新.
            // 要是放在里面出窗口的时候在更新, 假如全是无重复的就不会更新结果了)
            ret = Math.max(right - left + 1, ret);
        }
        return ret;
    }


    public int lengthOfLongestSubstring1(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        // value 是次数
        Map<Character, Integer> hash = new HashMap<>();
        int left = 0, right = 0, ret = 0;
        // 遍历字符数组
        for (right = 0; right < n; right++) {
            char c = ch[right];
            // 1. 进窗口
            hash.put(c, hash.getOrDefault(c, 0) + 1);
            // 2. 判断是否有重复字符
            if(hash.get(c) > 1) {
                // 3. 出窗口
                while(ch[left] != c) {
                    // 两种出窗口方式都可以
                    // hash.remove(ch[left]);
                    hash.put(ch[left], hash.getOrDefault(ch[left], 0) - 1);
                    left++;
                }
                // 多走一步, 这样就是合格的窗口
                left++;
            }
            // 4. 更新结果
            ret = Math.max(right - left + 1, ret);
        }
        return ret;
    }


}
